#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

typedef struct Stack {
    TreeNode* data[100];
    int top;
} Stack;

void push(Stack* stack, TreeNode* node) {
    stack->data[stack->top++] = node;
}

TreeNode* pop(Stack* stack) {
    return stack->data[--stack->top];
}

int isEmpty(Stack* stack) {
    return stack->top == 0;
}

void preorderTraversal(TreeNode* root) {
    Stack stack;
    stack.top = 0;

    TreeNode* node = root;
    while (node || !isEmpty(&stack)) {
        while (node) {
            printf("%d ", node->val);
            push(&stack, node);
            node = node->left;
        }
        node = pop(&stack);
        node = node->right;
    }
}

void inorderTraversal(TreeNode* root) {
    Stack stack;
    stack.top = 0;

    TreeNode* node = root;
    while (node || !isEmpty(&stack)) {
        while (node) {
            push(&stack, node);
            node = node->left;
        }
        node = pop(&stack);
        printf("%d ", node->val);
        node = node->right;
    }
}

void postorderTraversal(TreeNode* root) {
    Stack stack;
    stack.top = 0;
    TreeNode* prev = NULL;

    TreeNode* node = root;
    while (node || !isEmpty(&stack)) {
        while (node) {
            push(&stack, node);
            node = node->left;
        }
        node = stack.data[stack.top - 1]; // Peek the top element
        if (node->right == NULL || node->right == prev) {
            printf("%d ", node->val);
            pop(&stack);
            prev = node;
            node = NULL;
        } else {
            node = node->right;
        }
    }
}
